1. Field of the Invention
Embodiments of this invention are related to storing values in memory.
2. Background Art
Packet processing devices, such as routers, switches, bridges, and the like, are required to accommodate increasing bandwidth and processing requirements. For example, increases in bandwidth requires that each packet is processed in a packet processing device at near wire speeds, while simultaneously the number of packets entering the packet processing device gets larger. Moreover, complex packet processing may require the packet processing device to compare larger groups of fields in packet headers to preconfigured values.
In many packet processing devices, packet header fields are compared to entries in a ternary content accessible memory (TCAM). A TCAM is a table of entries in which values can be stored using binary (e.g., 1 and 0) bits as well as wildcard bits. A “wildcard” indicates that the corresponding bit can be a 1 or a 0. Some specific techniques by which 1, 0, and wildcards are stored are known in the art and may be implementation dependent. Each entry in a TCAM may correspond to one or more fields. An incoming packet may be compared to all entries in a TCAM in parallel. Other memory data structures, too, may be used in performing lookup based upon incoming packet fields.
Examined packet header fields can include Internet Protocol (IP) addresses, port values, protocol values, virtual local area network identifiers (VLANID), and other header fields. Some of the header fields are compared to specific values. Other header fields may be compared to ranges of values. Ranges of IP addresses can often be represented using common prefixes. A “prefix” is a sequence of one or more bits starting at the beginning of a binary representation of a value. As used herein, two or more values are said to have a common prefix if the binary representation of each value has a sequence of one or more bits starting at the first bit common with others in the two or more values. However, ranges of integer values (such as that used to represent port values, protocol identifiers, etc. in packet headers) may not be represented efficiently using prefixes. For example, storing a range of values may require a relatively high number of prefixes, and each prefix may require multiple entries in a TCAM. Each prefix for the range, for example, may require multiple TCAM entries in order to be compared in combinations of other fields.
Thus, the number of entries required in TCAM and other lookup structures in memory to store ranges of values may be excessive. TCAMs are frequently used for lookup operations due to their speed and flexibility. However, due to the relatively high power consumption and cost of TCAMs, a need exists to reduce the size of the TCAMs. Other memory too can be used for lookup, and can yield benefits from having fewer entries in lookup tables.